/*
*	FloodFill 算法(洪水灌溉)
*/


//图形渲染
//https://leetcode.cn/problems/flood-fill/description/
// class Solution {
//     int m = 0,n = 0,target = 0,cor = 0;
//     int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
// public:
//     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//         if(image[sr][sc] == color) return image;
//         m = image.size(),n = image[0].size(),target = image[sr][sc],cor = color;
//         image[sr][sc] = color;
//         dfs(image,sr,sc);
//         return image;
//     }

//     void dfs(vector<vector<int>>& image, int sr, int sc)
//     {
//         image[sr][sc] = cor;
//         for(int i = 0;i<4;++i)
//         {
//             int px = sr + dx[i],py = sc + dy[i];
//             if(px < m && px >= 0 && py < n && py >= 0 && target == image[px][py]) dfs(image,px,py);
//         }
//     }
// };


//岛屿数量
//https://leetcode.cn/problems/number-of-islands/submissions/
// class Solution {
//     vector<vector<bool>> check;
//     int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
//     int m = 0, n = 0;
//     int ret = 0;
// public:
//     int numIslands(vector<vector<char>>& grid) {
//         m = grid.size(), n = grid[0].size();
//         check.resize(m,vector<bool>(n,false));
//         for(int i = 0;i<m;++i)
//             for(int k = 0;k<n;++k)
//                 if(!check[i][k] && grid[i][k] == '1') 
//                 {
//                     check[i][k] = true;
//                     dfs(grid,i,k);
//                     ++ret;
//                 }
//         return ret;
//     }

//     void dfs(vector<vector<char>>& grid,int x,int y)
//     {
//         for(int i = 0;i<4;++i)
//         {
//             int px = x + dx[i],py = y + dy[i];
//             if(px < m && px >= 0 && py < n && py >= 0 && !check[px][py] && grid[px][py] == '1')
//             {
//                 check[px][py] = true;
//                 dfs(grid,px,py);
//             }
//         }
//     }
// };


//岛屿的最大面积
//https://leetcode.cn/problems/max-area-of-island/submissions/
// class Solution {
//     vector<vector<bool>> check;
//     int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
//     int m = 0, n = 0;
//     int ret = 0;
//     int count = 0;
// public:
//     int maxAreaOfIsland(vector<vector<int>>& grid) {
//         m = grid.size(), n = grid[0].size();
//         check.resize(m,vector<bool>(n,false));
//         for(int i = 0;i<m;++i)
//             for(int k = 0;k<n;++k)
//                 //找到一个岛屿的入口点 然后求岛屿面积
//                 if(!check[i][k] && grid[i][k] == 1) 
//                 {
//                     check[i][k] = true;
//                     dfs(grid,i,k);
//                     ret = max(ret,count);
//                     count = 0;
//                 }
//         return ret;
//     }

//     void dfs(vector<vector<int>>& grid,int x,int y)
//     {
//         ++count;
//         for(int i = 0;i<4;++i)
//         {
//             int px = x + dx[i],py = y + dy[i];
//             if(px < m && px >= 0 && py < n && py >= 0 && !check[px][py] && grid[px][py] == 1)
//             {
//                 check[px][py] = true;
//                 dfs(grid,px,py);
//             }
//         }
//     }
// };


//被围绕的区域
//https://leetcode.cn/problems/surrounded-regions/
// class Solution {
//     int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};
//     int m = 0,n = 0; 
// public:
//     void solve(vector<vector<char>>& board) {
//         m = board.size(),n = board[0].size();
//         //先标记边界区域 再通过标记区分边界和被围的区域
//         for(int i = 0;i<n;++i)
//         {
//             if(board[0][i] == 'O') dfs(board,0,i);
//             if(board[m-1][i] == 'O') dfs(board,m-1,i);
//         }
//         for(int i = 0;i<m;++i)
//         {
//             if(board[i][0] == 'O') dfs(board,i,0);
//             if(board[i][n-1] == 'O') dfs(board,i,n-1);
//         }

//         for(int i = 0;i<m;++i)
//             for(int k = 0;k<n;++k)
//             {
//                 if(board[i][k] == 'O') board[i][k] = 'X';
//                 else if(board[i][k] == '.') board[i][k] = 'O';
//             }
//     }

//     void dfs(vector<vector<char>>& board,int x,int y)
//     {
//         board[x][y] = '.';
//         for(int i = 0;i<4;++i)
//         {
//             int px = x+dx[i],py = y+dy[i];
//             if(px < m && px >= 0 && py < n && py >= 0 && board[px][py] == 'O') dfs(board,px,py);
//         }
//     }
// };


//太平洋大西洋水流问题
//https://leetcode.cn/problems/pacific-atlantic-water-flow/
// class Solution {
//     int m = 0,n = 0;
//     int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
// public:
//     vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//         vector<vector<int>> ret;
//         m = heights.size(),n = heights[0].size();

//         //从太平洋开始一直走到山顶，上山，直到判断下山为止，此时山顶就是可以流向起始位置的下标
//         //两个bool数组分别标记可以流向的山顶 两个数组中重复标记的山顶就是既可以流向大西洋和太平洋的下标
//         vector<vector<bool>> pac(m,vector<bool>(n,false)); //太平洋标记数组
//         vector<vector<bool>> atl(m,vector<bool>(n,false)); //大西洋标记数组



//         //太平洋
//         for(int i = 0;i<m;++i) if(!pac[i][0]) dfs(heights,i,0,pac);
//         for(int i = 0;i<n;++i) if(!pac[0][i]) dfs(heights,0,i,pac);
//         //大西洋
//         for(int i = 0;i<m;++i) if(!atl[i][n-1]) dfs(heights,i,n-1,atl);
//         for(int i = 0;i<n;++i) if(!atl[m-1][i]) dfs(heights,m-1,i,atl);

//         for(int i = 0;i<m;++i)
//             for(int k = 0;k<n;++k)
//                 if(pac[i][k] && atl[i][k]) ret.push_back({i,k});

//         return ret;
//     }

//     void dfs(vector<vector<int>>& heights,int x,int y,vector<vector<bool>>& check)
//     {
//         check[x][y] = true;
//         for(int i = 0;i<4;++i)
//         {
//             int px = x+dx[i],py = y+dy[i];
//             if(px < m && px >= 0 && py < n && py >= 0 && !check[px][py] && heights[x][y]<=heights[px][py]) dfs(heights,px,py,check);
//         }
//     }
// };


//扫雷游戏
//https://leetcode.cn/problems/minesweeper/description/
// class Solution {
//     int dx[8] = {-1,-1,-1,0,0,1,1,1},dy[8] = {-1,0,1,-1,1,-1,0,1};
//     int m = 0,n = 0;
// public:
//     vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
//         m = board.size(),n = board[0].size();
//         dfs(board,click[0],click[1]);
//         return board;
//     }

//     //return true 挖到地雷
//     //return false 没有挖到地雷
//     void dfs(vector<vector<char>>& board,int x,int y)
//     {
//         if(board[x][y] == 'M')
//         {
//             board[x][y] = 'X';
//             return;
//         }
//         else if(board[x][y] == 'E')
//         {
//             int count = 0;
//             for(int i = 0;i<8;++i)
//             {
//                 int px = x+dx[i],py = y+dy[i];
//                 if(px < m && px >= 0 && py < n && py >=0 && (board[px][py] == 'M' || board[px][py] == 'X')) ++count;
//             }
//             if(count) board[x][y] = count + '0';
//             else 
//             {
//                 board[x][y] = 'B';

//                 for(int i = 0;i<8;++i)
//                 {
//                     int px = x+dx[i],py = y+dy[i];
//                     if(px < m && px >= 0 && py < n && py >=0 && board[px][py] != 'B') dfs(board,px,py);
//                 }
//             }
//         }
//     }
// };


//衣橱整理
//https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/submissions/
// class Solution {
//     int ret = 0;
//     int _m = 0,_n = 0,target = 0;
//     vector<vector<bool>> grid;
// public:
//     int wardrobeFinishing(int m, int n, int cnt) {
//         grid.resize(m,vector<bool>(n));
//         _m = m,_n = n,target = cnt;
//         dfs(0,0);
//         return ret;
//     }

//     bool check(int x,int y)
//     {
//         int num = 0;
//         while(x)
//         {
//             num += x%10;
//             x/=10;
//         }
//         while(y)
//         {
//             num += y%10;
//             y/=10;
//         }
//         if(num <= target) return true;
//         return false;
//     }

//     void dfs(int x,int y)
//     {
//         grid[x][y] = true;
//         //注意:如果该格子不满足 则后面的格子无法到达
//         if(check(x,y)) ++ret;
//         else return;

//         if(x+1<_m && !grid[x+1][y]) dfs(x+1,y);
//         if(y+1<_n && !grid[x][y+1]) dfs(x,y+1);
//     }
// };


